
#ifndef FAST_VECTOR
#define FAST_VECTOR

#include <iostream>
#include <map>


//
//struct IndexCache {
//    size_t ind;
//    size_t rInd;
//};
//int searchInsertLeft( size_t size, IndexCache nums[], size_t target ) {
//    if ( size == 0 ) {
//        return 0;
//    }
//
//    // ����
//    if ( nums[size - 1].ind < target ) {
//        return size;
//    }
//    int left = 0;
//    int right = size - 1;
//    while ( left < right ) {
//        int mid = left + ( right - left ) / 2;
//        // �ϸ�С�� target ��Ԫ��һ�����ǽ�
//        if ( nums[mid].ind < target ) {
//            // ��һ������������ [mid + 1, right]
//            left = mid + 1;
//        }
//        else {
//            // ��һ������������ [left, mid] 
//            right = mid;
//        }
//    }
//    return left;
//};
//int searchInsertRight( size_t size, IndexCache nums[], size_t target ) {
//    if ( size == 0 ) {
//        return 0;
//    }
//
//    // ����
//    if ( nums[size - 1].ind < target ) {
//        return size;
//    }
//    int left = 0;
//    int right = size - 1;
//    while ( left < right ) {
//        int mid = left + ( right - left ) / 2;
//        // �ϸ�С�� target ��Ԫ��һ�����ǽ�
//        if ( nums[mid].ind < target ) {
//            // ��һ������������ [mid + 1, right]
//            left = mid + 1;
//        }
//        else {
//            // ��һ������������ [left, mid] 
//            right = mid;
//        }
//    }
//    return right;
//};

template<typename T>
class FastVector {
    size_t __ignoreCount;

    char *__delMark;
    size_t __delMarkSize;
    size_t __delMarkCount;
    void __gc() {
        if ( __delMarkCount < (int)(__delMarkSize / 10) || __ignoreCount < 300 ) {
            return;
        }
        __ignoreCount = 0;
        T* newArr = new T[_vecSize];
        size_t newInd = 0;
        size_t vecCount = _vecCount;
        for ( size_t i = 0; i < vecCount; i++ ) {
            if ( !__delMark[i] ) {
                newArr[newInd] = _vec[i];
                newInd++;
            }
        }
        delete[] _vec;
        _vec = newArr;

        delete[] __delMark;
        MALLOC( __delMark, char, __delMarkSize, 0 );
        __delMarkCount = 0;
    }
    inline void __mallocVec( size_t newCount ) {
        if ( _vecSize < newCount ) {
            _vecSize = newCount * 2;
            T *newVec = new T[_vecSize];
            COPY( _vec, newVec, sizeof( T )*newCount );

            delete[] _vec;
            _vec = newVec;
        }
    }
    inline void __mallocMark( size_t newCount ) {
        if ( __delMarkSize < newCount ) {
            char *_newMark;
            __delMarkSize = newCount * 2;
            MALLOC( _newMark, char, __delMarkSize, 0 );
            COPY( __delMark, _newMark, sizeof( char )*newCount );

            delete[] __delMark;
            __delMark = _newMark;
        }
    }
    inline size_t __findReadIndex( size_t ind ) {
        __gc();
        if ( __delMarkCount == 0 ) {
            return ind;
        }
        size_t cur = 0;
        size_t realInd = 0;
        size_t count = _vecCount + __delMarkCount;
        //realInd >= ind
        for ( size_t i = ind; i < count;i++) {
            if ( __delMark[i] ) {
                __ignoreCount++;
                continue;
            }
            if ( cur == ind ) {
                realInd = i;
                break;
            }
            cur++;
        }

        return realInd;
    }
protected:
    T* _vec;
    size_t _vecSize;
    size_t _vecCount;
public:
    bool has( T const& tar ) {
        __gc();
        size_t count = __delMarkCount + _vecCount;
        for ( size_t i = 0; i < count; i++ ) {
            if ( __delMark[i] ) {
                __ignoreCount++;
                continue;
            }
            if ( _vec[i] == tar ) {
                return true;
            }
        }
        return false;
    }
    FastVector( size_t size = DEFAULT_SIZE ) {
        _vec = new T[size];
        MALLOC( __delMark, char, size, 0 );
        _vecSize = size;
        _vecCount = 0;
        __delMarkSize = size;
        __delMarkCount = 0;
        __ignoreCount = 0;
    }
    ~FastVector() {
        delete[] _vec;
        delete[] __delMark;
    }
    inline size_t count() const {
        size_t count = _vecCount;
        //-(-total+deled) = count;
        return count - __delMarkCount;
    }
    FastVector& add( T cell ) {
        size_t sizeNeed = _vecCount + 1;
        __mallocVec( sizeNeed );
        _vec[sizeNeed - 1] = cell;
        _vecCount++;

        __mallocMark( sizeNeed );
        __delMark[sizeNeed - 1] = 0;

        return *this;
    }
    FastVector& del( size_t ind ) {
        if ( __delMark[ind] ) {
            return *this;
        }
        __delMark[ind] = 1;
        __delMarkCount++;
        _vecCount--;
        __gc();
        return *this;
    }
    FastVector& insert( size_t ind, T cell ) {
        if ( this->count() <= ind ) {
            add( cell );
            return *this;
        }
        int rInd = __findReadIndex( ind );

        if ( rInd-1 >= 0 && __delMark[rInd-1] ) {
            _vec[rInd - 1] = cell;
            __delMark[rInd - 1] = 0;
            __delMarkCount--;
        }
        else {
            //( 2, 2 )
            //     2
            // 1,2,2,3,5,5
            // 0,0,0,0,1,0
            size_t sizeNeed = _vecCount+__delMarkCount + 1;
            __mallocVec( sizeNeed );
            for ( int i = sizeNeed - 2; i >= rInd; i-- ) {
                if ( __delMark[i] ) {
                    continue;
                }
                _vec[i + 1] = _vec[i];
            }
            _vec[rInd] = cell;

            __mallocMark( sizeNeed );
            for ( int i = sizeNeed - 2; i >= rInd; i-- ) {
                __delMark[i + 1] = __delMark[i];
            }
            __delMark[rInd] = 0;
        }

        _vecCount++;
        return *this;
    }
    T& operator[] ( size_t ind ) {
        size_t rInd = __findReadIndex( ind );
        return _vec[rInd];
    }
    void info() {
        std::cout << "members:";
        for ( size_t i = 0; i < _vecCount; i++ ) {
            size_t rInd = __findReadIndex( i );
            std::cout << _vec[rInd];
        }
        std::cout << " count:" << _vecCount << std::endl;
    }
};

#endif //FAST_VECTOR